The present invention relates generally to electronic cryptography technology, and in particular to protecting a security device against side-channel attacks directed against computations of the Extended Euclidean Algorithm during decryption operations.
Electronic communication and commerce can be powerful yet dangerous tools. With the wide-spread availability of network technology, such as the Internet, there is an ever increasing use of online tools for communication and commerce. Every year more users find it easier or quicker to conduct important transactions, whether in the form of correspondence or commerce, using computers and computer networks. However, there is always the risk that the security of electronic transactions is compromised through interception by third parties who do not have the right to partake in the transactions. When malicious third parties obtain access to otherwise private transactions and data there is risk of economic loss, privacy loss, and even loss of physical safety. Cryptography is one mechanism employed to avoid intrusion into the privacy of electronic transactions and data.
Cryptography is a technology for hiding a message in the presence of third parties using mathematical techniques in which a message is encrypted in such a way that it can only be decrypted using a secret key that should only be known by the recipient and/or sender of a message.
Cryptographic algorithms have inputs and outputs. In the case of encryption, the input is a message that is to be protected in plaintext. The plaintext message is manipulated by the cryptographic algorithm to produce a ciphertext, the output. To produce the ciphertext the cryptographic algorithm performs certain mathematical operations that include the use of a secret key. The key may be a shared secret, e.g., between a sender and recipient, or may be a private key held by the recipient.
Traditionally, both sender and recipient of a cryptographic message was considered secure. Cryptography's primary use was to transmit an encoded message from the sender to the recipient without fear that an intermediary would be able to decode the message. If an attacker has no access to the sender's or recipient's cryptography devices, the attacker is limited to using the encoded message itself, or possible an encoded message and a corresponding plaintext message, to discern the cryptographic key used to encode or decode the message. However, if the attacker has access to the cryptographic device, the picture changes dramatically.
One mechanism of ensuring that a private key is indeed kept private is to store the private key and any related key material on a secure portable device, e.g., a smart card or a mobile device. A smart card is a small tamper resistant computer often in the form of a credit card sized and shaped package. Smart cards may be used to store cryptographic keys and cryptography engines for performing encryption, decryption, and digital signatures.
In one example, a user may receive an encrypted message and uses his smart card to decrypt the message by first authenticating to the smart card and then passing the message to the smart card for decryption. If authentication is successful, the smart card may use a cryptographic key stored on the card, and a corresponding cryptography engine, to decrypt the message and provide the decrypted message to the user. Similarly, if a user wishes to cryptographically sign a message, the user may pass the message to the user's smart card, which uses a cryptographic key of the user to digitally sign the message and to provide the signature back to the user or to a third party recipient.
If an attacker has access to the smart card, the attacker may make repeated observations of the execution of the cryptographic algorithms that may be used to discern the secrets stored on the smart card, specifically secret cryptographic keys stored on the smart card. One such attack is the so-called side-channel attack.
Side-channel attacks make use of the program timing, power consumption and/or the electronic emanation of a device that performs a cryptographic computation. The behavior of the device (timing, power consumption and electronic emanation) varies and depends directly on the program and on the data manipulated in the cryptographic algorithm. An attacker could take advantage of these variations to infer sensitive data leading to the recovery of a private key.
Many currently popular assymetric crypto systems, e.g., the RSA ([Rivest] Rivest, Shamir, and Adleman (A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, MIT Memo MIT/LCS/TM-82, 1977. https://people.csail.mit.edu/rivest/Rsapaper.pdf, accessed, Mar. 10, 2016), derive their security from the difficulty of factoring integers and finding the discrete log of a number. However, such systems are somewhat inefficient due to the requirement of raising a number to a power and their cryptographic primitives are somewhat vulnerable to attack on quantum computers. For example, integer factorization of products of large prime numbers, the foundation of many public key cryptography systems, is considered computationally infeasible on ordinary digital computers, yet may be solved relatively efficiently on quantum computers.
Code based cryptography, introduced by R. McEliece in 1978 is a potential candidate to replace the asymmetric primitives, which are threatened by quantum computers ([McEliece] McEliece, Robert J. (1978). “A Public-Key Cryptosystem Based On Algebraic Coding Theory” (PDF). DSN Progress Report 44: 114-116. Bibcode: 1978DSNPR . . . 44 . . . 114M, http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF, accessed on, Mar. 16, 2016). The family of codes proposed by McEliece, namely the binary Goppa codes has been considered secure for more than 30 years and allows very fast encryption. Relying on other assumptions than number-theory problems such as the discrete logarithm problem and integer factorization is a very positive characteristic of code based primitives. Its major drawback lies in the size of the public keys.
Code-based cryptography relies on the hardness of decoding, that is recovering a message m and an error e when given only the encoded message c, where c=mG+e and G (for m in Fqk, G in Fqkn and e in Fqn). The error weight is critical for security. Contrary to the public parameters of the code, which are fixed at set up by an external entity, the error may vary at each encryption, and may even be chosen by any public user in some situations.
One drawback to code based cryptography is vulnerability to side-channel attacks. The vulnerability arises in most of the implementations of McEliece cryptography, because the operation flow of the decryption is strongly influenced by the error vector, but no information is known about the error vector when starting decryption. From an attacker's point of view, this is a favorable situation. It means that the observed or manipulated device may leak information before any detection of the attack. These security aspects were addressed by various authors, who explained that a device implementing an unprotected decryption is prone to attacks on the messages (see e.g., [Shofan] A. Shoufan, F. Strenzke, H. G. Molter, and M. Stottinger. A Timing Attack against Patterson Algorithm in the McEliece P K C. In D. Lee and S. Hong, editors, ICISC, volume 5984 of Lecture Notes in Computer Science, pages 161-175. Springer, 2009; [Avanzi] R. Avanzi, S. Hoerder, D. Page, and M. Tunstall. Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems. J. Cryptographic Engineering, 1(4):271-281, 2011). and on the key (See e.g., [Strenzke 2010] F. Strenzke. A Timing Attack Against the Secret Permutation in the Mceliece PKC. In Proceedings of the Third International Conference on Post-Quantum Cryptography, PQCrypto'10, pages 95-107, Berlin, Heidelberg, 2010. Springer-Verlag; [Strenzke 2013] F. Strenzke. Timing Attacks against the Syndrome Inversion in Code-Based Cryptosystems. In P. Gaborit, editor, PQCrypto, volume 7932 of Lecture Notes in Computer Science, pages 217-230. Springer, 2013.). Although countermeasures were proposed against some of the leakages, the situation is still unsatisfactory, as it is noticed in the conclusion of [Strenzke 2013].
The McEliece Cryptosystem is described in [Au] Au, Susanne et al., The McEliece Cryptosystem, http://www.math.uml.edu/˜s-jeverso2/McElieceProject.pdf, accessed on Mar. 10, 2016 and in [Georgieva] Georgieva, Mariya and de Portzamparc, Frédéric, Toward Secure Implementation of McEliece Decryption, COSADE 2015, https://www.cosade.org/proceedings/paper_S04_3.pdf, accessed on Mar. 10, 2016, incorporated herein by reference.
In summary, in the McEliece cryptosystem, decoding of an encoded message c requires the determination of the error e. The principal methods for obtaining the error e include using the Extended Euclidean Algorithm (EEA) to compute an error locator polynomial σ(z). More details of the EEA are provided herein below. The EEA is particularly vulnerable to side-channel attacks, for example, because the execution time of the EEA depends on the Hamming weight of the error e. Thus, side-channel leakages may be used to deduce possible values for e.
Prior efforts to protect a cryptography device performing McEliece decryption include efforts to ensure that the EEA computation performs a computation both on the ciphertext c and on a twisted ciphertext c*i such that the execution time for c and c*i are the same ([Shoufan]). However, such a defense does not protect against other leakages besides execution time.
Strenske ([Strenzke 2013] and [Strenske 2010] studied the security execution of the McEliece decryption in the special case of decoding errors of weight 4 or 6. However, Strenske did not provide a countermeasure applicable to the general case.
From the foregoing it will be apparent that, while McEliece cryptography provides an attractive alternative to RSA and other popular assymetric cryptography systems, there is still a need for an improved technology to provide a secure mechanism that is computationally efficient, that does not provide side-channel leakage that may be exploited in side-channel attacks to deduce the error e in the encoding of a message m when performing cryptographic operations using the Extended Euclidean Algorithm, for example, decryption of McEliece codes.